#include <iostream>
using namespace std;
/// @brief 辅助数组B
int *B = (int *)malloc(sizeof(int));
/// @brief A[low...mid]和A[mid+1...high]各自有序，将两个部分归并
/// @param A
/// @param low
/// @param mid
/// @param high
void Merge(int A[], int low, int mid, int high)
{
    int i, j, k;
    // 将[low,high]内的元素复制到辅助数组B
    for (k = low; k <= high; k++)
    {
        B[k] = A[k]; // 将A中所有元素复制到B中
    }
    // 归并
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)
    {
        // 两个元素相等时，优先使用靠前的那个（稳定性）
        if (B[i] <= B[j])
        { // 将较小值复制到A中
            A[k] = B[i++];
        }
        else
        {
            A[k] = B[j++];
        }
    }
    // 将没有归并完的部分复制到尾部
    while (i <= mid)
    {
        A[k++] = B[j++];
    }
    while (j <= high)
    {
        A[k++] = B[j++];
    }
}

void MergeSort(int A[], int low, int high)
{
    if (low < high)
    {
        int mid = (low + high) / 2; // 从中间划分
        // 对左右两个子序列分别进行归并排序
        MergeSort(A, low, mid);      // 对左半部分归并排序
        MergeSort(A, mid + 1, high); // 对右半部分归并排序
        // 左右两个子序列分别有序之后再将二者归并
        Merge(A, low, mid, high); // 归并
    }
}